package puzzle.puzzleup2009;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Boat {

	/**
	 * 左岸是需要过河的人集合，记为L(EFT)，右岸是已经过河的人集合，记为R(IGHT)。
	 * 船的状态记为B， B可以是l (船在左岸) , r (船在右岸)
	 * 状态记为(L, R, B)。
	 * 初始状态 S = ({A,B,C,D,E}, {}, l)，目标状态 E = ({}, {A,B,C,D,E}, r)
	 * 一共有2*2^5 = 64种状态。
	 * 
	 * 可以互相转换的状态之间用边相连:
	 * a) 不是任何两个状态之间都有边相连，所以不能保证所有状态都是可达的;
	 * b) 相邻的状态(L1, R1, B1)，(L2, R2, B2)满足B1 != B2;
	 * c) 相邻的状态(L1, R1, B1)，(L2, R2, B2)之间可能存在多种转换方式;
	 * 
	 * 所以，这里边的权重是状态转换所需要的最小时间。
	 * 
	 * 这个图是一个有向图。
	 * 
	 * 我们试图找到从S到E的最短路径。
	 * 
	 * 注意：下面的论断是否正确？
	 * 1. 每次从左岸到右岸，船上一定是两个人，而返回时，一定是一个人。
	 * 
	 * tags: Graph
	 * @param args
	 */
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {

		State S = new State();
		S.L.add(new Person("A", 11));
		S.L.add(new Person("B", 7));
		S.L.add(new Person("C", 4));
		S.L.add(new Person("D", 2));
		S.L.add(new Person("E", 1));
		S.boat = 'l';

		State E = new State();
		E.R.add(new Person("A", 11));
		E.R.add(new Person("B", 7));
		E.R.add(new Person("C", 4));
		E.R.add(new Person("D", 2));
		E.R.add(new Person("E", 1));
		E.boat = 'r';
		
		
		//distances from S to each state
		List<State> states = new ArrayList<State>();
		states.add(S);
		List<Integer> distances = new ArrayList<Integer>();
		distances.add(0);
		List<List<State>> paths = new ArrayList<List<State>>();
		paths.add(new ArrayList<State>());

		int count = 64;
		while (count > 0) {
			for (int k = 0; k < states.size(); k ++) {
				State s = states.get(k);
				Integer curDist = distances.get(k);
				Object[] next = s.next();
				List<State> nextStates = (List<State>)next[0];
				List<Integer> nextDist = (List<Integer>)next[1];
				for (int i = 0; i < nextStates.size(); i ++) {
					State n = nextStates.get(i);
					int j = -1;
					for (int x = 0; x < states.size(); x ++) {
						if (states.get(x).equals(n)) {
							j = x;
							break;
						}
					}
					if (j != -1) {
						if (nextDist.get(i) + curDist < distances.get(j)) {
							distances.set(j, nextDist.get(i) + curDist);
							List<State> path = new ArrayList<State>();
							path.addAll(paths.get(k));
							path.add(n);
							paths.set(j, path);
						}
					} else {
						states.add(n);
						distances.add(nextDist.get(i) + curDist);
						List<State> path = new ArrayList<State>();
						path.addAll(paths.get(k));
						path.add(n);
						paths.add(path);
					}
				}
			}
			count --;
		}
		
		int j = -1;
		for (int x = 0; x < states.size(); x ++) {
			if (states.get(x).equals(E)) {
				j = x;
				break;
			}
		}
		System.out.println(distances.get(j));
		System.out.println(paths.get(j));
	}
	
	private static class Person implements Comparable<Person> {
		
		String name;
		Integer time;
		
		public Person(String name, Integer time) {
			this.name = name;
			this.time = time;
		}
		
		@Override
		public String toString() {
			return this.name + this.time;
		}
		
		@Override
		public boolean equals(Object obj) {
			
			if (obj instanceof Person) {
				Person p = (Person)obj;
				return p.name.equals(this.name);
			}
			return false;
		}
		
		public int compareTo(Person o) {
			return this.name.compareTo(o.name);
		}
		
		@Override
		public Object clone() {
			return new Person(this.name, this.time);
		}
		
		public static List<Person> clone(List<Person> ps) {
			
			List<Person> t = new ArrayList<Person>();
			for (Person p: ps) {
				t.add((Person)p.clone());
			}
			return t;
		}
	}
	
	private static class State {
		
		List<Person> L = new ArrayList<Person>();
		List<Person> R = new ArrayList<Person>();
		char boat;
		
		@Override
		public String toString() {
			return "(" + L + "," + R + "," + boat + ")";
		}
		
		@Override
		public boolean equals(Object obj) {
			
			if (obj instanceof State) {
				State s = (State)obj;
				return s.boat == this.boat 
					&& equals(s.L, this.L)
					&& equals(s.R, this.R);
			}
			return false;
		}
		
//		@Override
//		public int hashCode() {
//
//			return this.toString().hashCode();
//		}
		
		private boolean equals(List<Person> X, List<Person> Y) {
			
			if (X.size() != Y.size()) {
				return false;
			} else {
				Collections.sort(X);
				Collections.sort(Y);
				for (int i = 0; i < X.size(); i ++) {
					if (!X.get(i).equals(Y.get(i))) {
						return false;
					}
				}
				return true;
			}
		}
		

		
		/**
		 * 获得当前状态可能的下一个状态。
		 * 有四种可能：
		 * 1) B = l
		 * 	1.1) L中有一个人划船到右岸
		 * 	1.2) L中有两个人划船到右岸
		 * 2) B = r
		 * 	2.1) R中有一个人划船到左岸
		 * 	2.2) R中有两个人划船到左岸
		 * @return
		 */
		public Object[] next() {
			
			List<State> list = new ArrayList<State>();
			List<Integer> cost = new ArrayList<Integer>();
			if (this.boat == 'l') {
				//L中有一个人划船到右岸
				for (int i = 0; i < L.size(); i ++ ) {
					State s = new State();
					s.boat = 'r';
					s.L = Person.clone(this.L);
					s.R = Person.clone(this.R);
					Person pi = s.L.remove(i);
					s.R.add(pi);
					list.add(s);
					
					cost.add(pi.time);
				}
				//L中有两个人划船到右岸
				for (int i = 0; i < L.size(); i ++ ) {
					for (int j = i+1; j < L.size(); j ++ ) {
						State s = new State();
						s.boat = 'r';
						s.L = Person.clone(this.L);
						s.R = Person.clone(this.R);
						Person pi = s.L.remove(i);
						Person pj = s.L.remove(j-1);//not j, is j-1
						s.R.add(pi);
						s.R.add(pj);
						list.add(s);
						
						cost.add(Math.abs(pi.time - pj.time));
					}
				}
			} else {	//this.boat == 'r'
				//R中有一个人划船到右岸
				for (int i = 0; i < R.size(); i ++ ) {
					State s = new State();
					s.boat = 'l';
					s.L = Person.clone(this.L);
					s.R = Person.clone(this.R);
					Person pi = s.R.remove(i);
					s.L.add(pi);
					list.add(s);
					
					cost.add(pi.time);
				}
				//R中有两个人划船到右岸
				for (int i = 0; i < R.size(); i ++ ) {
					for (int j = i+1; j < R.size(); j ++ ) {
						State s = new State();
						s.boat = 'l';
						s.L = Person.clone(this.L);
						s.R = Person.clone(this.R);
						Person pi = s.R.remove(i);
						Person pj = s.R.remove(j-1);//not j, is j-1

						s.L.add(pi);
						s.L.add(pj);
						list.add(s);
						
						cost.add(Math.abs(pi.time-pj.time));
					}
				}
			}
			return new Object[] {list, cost};
		}
	}

}
